package 二叉树的所有路径;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {
    /*
    给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
    叶子节点 是指没有子节点的节点。
     */
    public List<String> binaryTreePaths(TreeNode root) {
        // 递归
        // 参数：TreeNode, path, List<path>
        // 返回值：void(遍历到叶子节点只代表找到了一条路径，递归返回值只有一个，但路径却存在多个)
        // 终止条件：root == null
        // 单层递归逻辑：递归遍历左右子树
        // 如果当前节点左右孩子都为null则需要返回该路径
        // 如果当前节点不为叶子节点，则继续拼接字符串递归
        if (root == null)
            return Collections.emptyList() ;
        List<String> paths = new ArrayList<String>();
        searchPaths(root, "", paths);
        return paths;
    }

    public void searchPaths(TreeNode root, String path, List<String> paths) {
        // 减少了 substring的使用
        if(path.isEmpty())
            path = String.valueOf(root.val);
        else
            path += "->" + root.val;

        if (root.left == null && root.right == null)
            paths.add(path); // 记录路径
        else {
            if (root.left != null)
                searchPaths(root.left, path, paths);
            if (root.right != null)
                searchPaths(root.right, path, paths);
        }
    }

}
